#![allow(dead_code)]
use std::fmt::Display;
use std::ops::DerefMut;
use std::{cmp::Ordering, ops::Deref};

use crate::stools::{random_array, random_num};

pub type Link = Option<Box<Node>>;

#[derive(Debug)]
pub struct Node {
    pub elem: i32,
    pub next: Link,
}

impl Node {
    pub fn new(elem: i32) -> Self {
        Self { elem, next: None }
    }
}

impl Display for List {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.head.is_none() {
            write!(f, "None")?;
            return Ok(());
        }

        write!(f, "[").unwrap();
        let mut curlink = self.head.as_ref();
        while let Some(curnode) = curlink {
            if curnode.next.is_none() {
                write!(f, "{}]", curnode.elem)?;
                break;
            }
            write!(f, "{} -> ", curnode.elem)?;
            curlink = curnode.next.as_ref();
        }

        Ok(())
    }
}

#[derive(Debug)]
pub struct List {
    pub head: Link,
}
impl Deref for List {
    type Target = Link;
    fn deref(&self) -> &Self::Target {
        &self.head
    }
}
impl DerefMut for List {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.head
    }
}
impl List {
    pub fn new() -> Self {
        Self { head: None }
    }

    fn from(&mut self, v: &[i32]) -> &mut Self {
        for e in v {
            self.push(*e);
        }
        self
    }

    pub fn push(&mut self, elem: i32) -> &mut Self {
        if self.head.is_none() {
            self.head = Some(Box::new(Node::new(elem)));
            return self;
        }

        let mut curlink = self.head.as_mut();
        while let Some(curnode) = curlink {
            if curnode.next.is_none() {
                curlink = Some(curnode);
                break;
            }
            curlink = curnode.next.as_mut();
        }
        curlink.map(|node| node.next = Some(Box::new(Node::new(elem))));

        self
    }

    fn tail(&mut self) -> Option<&mut Box<Node>> {
        let mut curlink = self.head.as_mut();

        while let Some(curnode) = curlink {
            if curnode.next.is_none() {
                curlink = Some(curnode);
                break;
            }
            curlink = curnode.next.as_mut();
        }

        curlink
    }

    fn rev(&mut self) -> &mut Self {
        let mut curlink = self.head.take();
        let mut prevlink: Option<Box<Node>> = None;
        let mut nextlink;

        while let Some(mut curnode) = curlink {
            nextlink = curnode.next;
            curnode.next = prevlink;
            prevlink = Some(curnode);
            curlink = nextlink;
        }

        self.head = prevlink;

        self
    }

    fn middle(&self) -> Option<&Box<Node>> {
        if self.head.is_none() {
            return None;
        }

        let mut slow = self.head.as_ref();
        let mut fast = self.head.as_ref();

        while let Some(fnode) = fast {
            fast = fnode.next.as_ref().and_then(|node| node.next.as_ref());
            slow = slow.unwrap().next.as_ref();
        }

        slow
    }

    fn is_palindrome(&self) -> bool {
        let mut stack = vec![];
        let mut curlink = self.head.as_ref();

        while let Some(curnode) = curlink {
            stack.push(curnode.elem);
            curlink = curnode.next.as_ref();
        }

        curlink = self.head.as_ref();
        while let Some(curnode) = curlink {
            let elem = stack.pop().unwrap();
            if elem != curnode.elem {
                return false;
            }
            curlink = curnode.next.as_ref();
        }

        true
    }
}

fn partition(nums: &mut [i32], num: i32) -> &mut [i32] {
    let mut nlt: usize = 0;
    let mut gt: usize = nums.len();
    let mut i: usize = 0;

    while i < gt {
        match nums[i].cmp(&num) {
            Ordering::Greater => {
                gt -= 1;
                nums.swap(i, gt);
            }
            Ordering::Equal => i += 1,
            Ordering::Less => {
                nums.swap(i, nlt);
                nlt += 1;
                i += 1;
            }
        }
    }

    nums
}

fn split_list(mut list: List, num: i32) -> List {
    let mut curlink = list.head.take();
    let mut v: Vec<i32> = vec![];

    while let Some(curnode) = curlink {
        v.push(curnode.elem);
        curlink = curnode.next;
    }

    partition(&mut v, num);
    for elem in v {
        list.push(elem);
    }

    list
}

/// 找到链表的最后一个节点
fn list_tail(link: &mut Link) -> &mut Box<Node> {
    let mut curlink = link.as_mut();

    while let Some(curnode) = curlink {
        if curnode.next.is_none() {
            curlink = Some(curnode);
            break;
        }
        curlink = curnode.next.as_mut();
    }

    curlink.unwrap()
}

/// 把节点加到链表的最后
fn append_list(mut curnode: Box<Node>, hd: &mut Link) -> Link {
    let next = curnode.next.take();
    if hd.is_none() {
        *hd = Some(curnode);
    } else {
        list_tail(hd).next = Some(curnode);
    }
    next
}

fn split_list2(list: &mut List, num: i32) -> List {
    let mut sh: Link = None;
    let mut eh: Link = None;
    let mut bh: Link = None;
    let mut curlink = list.head.take();

    while let Some(curnode) = curlink {
        let link = match curnode.elem.cmp(&num) {
            Ordering::Equal => &mut eh,
            Ordering::Greater => &mut bh,
            Ordering::Less => &mut sh,
        };
        curlink = append_list(curnode, link);
    }

    if sh.is_none() {
        sh = eh;
    } else {
        list_tail(&mut sh).next = eh;
    }
    if sh.is_none() {
        sh = bh;
    } else {
        list_tail(&mut sh).next = bh;
    }

    List { head: sh }
}

pub fn list1_main() {
    let mut list = List::new();
    list.push(1).push(6).push(3).push(4).push(10).push(100);

    println!("{}", list);
    println!("rev: {}", list.rev());
    println!("middle: {:?}", list.middle());
    println!("plindrome: {:?}", list.is_palindrome());

    let mut list = List::new();
    list.push(1).push(2).push(3).push(2).push(1);
    println!("plindrome: {:?}", list.is_palindrome());

    let mut list = List::new();
    list.from(&random_array(10, 0..10));
    println!("list: {}", list);
    let num = random_num(0..10);
    println!("num: {}", num);
    println!("{}", split_list(list, num));

    let mut list = List::new();
    list.from(&random_array(10, 0..10));
    println!("list: {}", list);
    let num = random_num(0..5);
    println!("num: {}", num);
    println!("{}", split_list2(&mut list, num));
}
